#ifndef cathlibcpp_vectorbool_H
#define cathlibcpp_vectorbool_H

// File:       vectorbool.h
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ vector<bool> specialization


#ifndef included_stddef_H
#define included_stddef_H
#include <stddef.h>            // for ptrdiff_t
#endif

#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_iterator_H
#include "iterator.h"
#endif

#ifndef cathlibcpp_utility_H
#include "utility.h"
#endif

#ifndef cathlibcpp_vector_H
#include "vector.h"
#endif


class vector_bool;
class vector_bool_reference;
class vector_bool_iterator;
class vector_bool_const_iterator;


// vector_bool_reference

class vector_bool_reference
{
  friend class vector_bool;
  friend class vector_bool_iterator;
  friend class vector_bool_const_iterator;

  public:

    // constructors
    ~vector_bool_reference()
      {}

    // mutators
    inline vector_bool_reference& operator=(bool rhs);

    void flip();

    // implicit conversion
    operator bool() const;

  private:

    vector_bool_reference(vector_bool* base, size_t pos)
      : base_(base),
        pos_(pos)
      {}

    vector_bool* base_;
    size_t pos_;
};


// vector_bool_iterator

class vector_bool_iterator : public random_access_iterator<bool>
{
  friend class vector_bool;

  friend ptrdiff_t operator-(vector_bool_iterator const& lhs, vector_bool_iterator const& rhs);

  public:

    // constructors
    vector_bool_iterator()
      {}
    vector_bool_iterator(vector_bool_iterator const& rhs)
      : base_(rhs.base_),
        pos_(rhs.pos_)
      {}

    // accessors
    bool operator==(vector_bool_iterator const& rhs) const
      { return pos_ == rhs.pos_ && base_ == rhs.base_; }

    vector_bool_reference operator*() const
      { return vector_bool_reference(base_, pos_); }

    vector_bool_iterator operator+(ptrdiff_t n) const
      { return vector_bool_iterator(base_, pos_+n); }

    vector_bool_iterator operator-(ptrdiff_t n) const
      { return vector_bool_iterator(base_, pos_-n); }

    vector_bool_reference operator[](ptrdiff_t n) const
      { return vector_bool_reference(base_, pos_+n); }

    // mutators
    vector_bool_iterator& operator=(vector_bool_iterator const& rhs)
      { base_ = rhs.base_; pos_ = rhs.pos_; return *this; }

    vector_bool_iterator& operator++()
      { ++pos_; return *this; }

    vector_bool_iterator operator++(int)
      { ++pos_; return vector_bool_iterator(base_, pos_-1); }

    vector_bool_iterator& operator--()
      { --pos_; return *this; }

    vector_bool_iterator operator--(int)
      { --pos_; return vector_bool_iterator(base_, pos_+1); }

    vector_bool_iterator& operator+=(ptrdiff_t n)
      { pos_ += n; return *this; }

    vector_bool_iterator& operator-=(ptrdiff_t n)
      { pos_ -= n; return *this; }

  private:

    vector_bool_iterator(vector_bool* base, size_t pos)
      : base_(base),
        pos_(pos)
      {}

    vector_bool* base_;
    size_t pos_;
};


inline ptrdiff_t operator-(vector_bool_iterator const& lhs, vector_bool_iterator const& rhs)
  { return lhs.pos_-rhs.pos_; }

// CFront can't work these out for itself
inline random_access_iterator_tag iterator_category(vector_bool_iterator const&)
  { return 0; }

inline bool* value_type(vector_bool_iterator const&)
  { return 0; }

inline ptrdiff_t* distance_type(vector_bool_iterator const&)
  { return 0; }


// vector_bool_const_iterator

class vector_bool_const_iterator : public random_access_iterator<bool const>
{
  friend class vector_bool;

  friend ptrdiff_t operator-(vector_bool_const_iterator const& lhs, vector_bool_const_iterator const& rhs);

  public:

    // constructors
    vector_bool_const_iterator()
      {}
    vector_bool_const_iterator(vector_bool_const_iterator const& rhs)
      : base_(rhs.base_),
        pos_(rhs.pos_)
      {}

    // accessors
    bool operator==(vector_bool_const_iterator const& rhs) const
      { return pos_ == rhs.pos_ && base_ == rhs.base_; }

    bool operator*() const;

    vector_bool_const_iterator operator+(ptrdiff_t n) const
      { return vector_bool_const_iterator(base_, pos_+n); }

    vector_bool_const_iterator operator-(ptrdiff_t n) const
      { return vector_bool_const_iterator(base_, pos_-n); }

    bool operator[](ptrdiff_t n) const;

    // mutators
    vector_bool_const_iterator& operator=(vector_bool_const_iterator const& rhs)
      { base_ = rhs.base_; pos_ = rhs.pos_; return *this; }

    vector_bool_const_iterator& operator++()
      { ++pos_; return *this; }

    vector_bool_const_iterator operator++(int)
      { ++pos_; return vector_bool_const_iterator(base_, pos_-1); }

    vector_bool_const_iterator& operator--()
      { --pos_; return *this; }

    vector_bool_const_iterator operator--(int)
      { --pos_; return vector_bool_const_iterator(base_, pos_+1); }

    vector_bool_const_iterator& operator+=(ptrdiff_t n)
      { pos_ += n; return *this; }

    vector_bool_const_iterator& operator-=(ptrdiff_t n)
      { pos_ -= n; return *this; }

  private:

    vector_bool_const_iterator(vector_bool const* base, size_t pos)
      : base_(base),
        pos_(pos)
      {}

    vector_bool const* base_;
    size_t pos_;
};


inline ptrdiff_t operator-(vector_bool_const_iterator const& lhs, vector_bool_const_iterator const& rhs)
  { return lhs.pos_-rhs.pos_; }

// CFront can't work these out for itself
inline random_access_iterator_tag iterator_category(vector_bool_const_iterator const&)
  { return 0; }

inline bool* value_type(vector_bool_const_iterator const&)
  { return 0; }

inline ptrdiff_t* distance_type(vector_bool_const_iterator const&)
  { return 0; }


// vector_bool

class vector_bool
{
  friend class vector_bool_reference;

  friend bool operator==(vector_bool const& lhs, vector_bool const& rhs);
  friend bool operator< (vector_bool const& lhs, vector_bool const& rhs);

  public:

    // CFront chokes on typedefs here.

#   define reference             vector_bool_reference
#   define const_reference       bool
#   define iterator              vector_bool_iterator
#   define const_iterator        vector_bool_const_iterator
#   define size_type             size_t
#   define difference_type       ptrdiff_t
#   define value_type            bool
#   define rev_iterator          reverse_iterator<iterator, value_type, reference>
#   define const_rev_iterator    reverse_iterator<const_iterator, value_type, const_reference>

    enum { npos = -1 };

    // constructors
    vector_bool();
    vector_bool(size_type n, bool value = false);
    vector_bool(bool const* first, bool const* last);
    vector_bool(vector_bool const& rhs);
    ~vector_bool();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    const_rev_iterator rbegin() const;
    const_rev_iterator rend() const;

    // non ANSI
    size_type find(bool b, size_type pos = 0) const;
    size_type rfind(bool b, size_type pos = npos) const;

    size_type size() const;
    size_type max_size() const;
    size_type capacity() const;

    bool empty() const;

    // non ANSI
    size_type count() const;

    const_reference operator[](size_type n) const;
    const_reference at(size_type n) const;

    const_reference front() const;
    const_reference back() const;

    // mutators
    vector_bool& operator=(vector_bool const& rhs);
    void assign(bool const* first, bool const* last);
    void assign(size_type n, bool t);

    iterator begin();
    iterator end();

    rev_iterator rbegin();
    rev_iterator rend();

    void resize(size_type sz, bool c = false);
    void reserve(size_type n);

    reference operator[](size_type n);
    reference at(size_type n);

    reference front();
    reference back();

    void push_back(bool x);
    void pop_back();

    iterator insert(iterator position, bool x);
    void insert(iterator position, size_type n, bool x = false);
    void insert(iterator position, bool const* first, bool const* last);

    void erase(iterator position);
    void erase(iterator first, iterator last);

    void swap(vector_bool& x);
    void swap(reference x, reference y);

    void clear();

    void flip();

  private:

    bool test(size_type pos) const;
    void set(size_type pos, bool b);
    void flip(size_type pos);

    void clear_overflow();

    vector<unsigned long> base_;
    size_type size_;

#   undef reference
#   undef const_reference
#   undef iterator
#   undef const_iterator
#   undef size_type
#   undef difference_type
#   undef value_type
#   undef rev_iterator
#   undef const_rev_iterator
};

bool operator==(vector_bool const& lhs, vector_bool const& rhs);
bool operator< (vector_bool const& lhs, vector_bool const& rhs);


// Implementation of vector_bool

#define reference             vector_bool_reference
#define const_reference       bool
#define iterator              vector_bool_iterator
#define const_iterator        vector_bool_const_iterator
#define size_type             size_t
#define difference_type       ptrdiff_t
#define value_type            bool
#define rev_iterator          reverse_iterator<iterator, value_type, reference>
#define const_rev_iterator    reverse_iterator<const_iterator, value_type, const_reference>

inline size_type vector_bool::size() const
  { return size_; }

inline bool vector_bool::empty() const
  { return size_ == 0; }

inline const_reference vector_bool::front() const
  { return at(0); }

inline const_reference vector_bool::back() const
  { return at(size_-1); }

#undef reference
#undef const_reference
#undef iterator
#undef const_iterator
#undef size_type
#undef difference_type
#undef value_type
#undef rev_iterator
#undef const_rev_iterator


// Implementation of vector_bool_reference

inline vector_bool_reference& vector_bool_reference::operator=(bool rhs)
  {
    base_->set(pos_, rhs);
    return *this;
  }

inline void vector_bool_reference::flip()
  { base_->flip(pos_); }

inline vector_bool_reference::operator bool() const
  { return base_->test(pos_); }

#endif
